import java.awt.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Vector;

class Delaunay{
	private final int INIT = 50;
	private int capacidadAristas;
	private Vector<Segment> segmentList;
	private HashSet<Point> points;
	private int segmentNum = 0;
	private Graph<Triangle> triGraph;

	HashSet<Triangle> triangles;

	private Point n, se, sw;

	private Triangle initialTriangle;

	public final Color COLOR_ARISTA = Color.black,
			COLOR_ARISTA_FLIP = Color.orange, COLOR_ARISTA_3 = Color.lightGray,
			COLOR_CIRCULO_ARISTA_PRUEBA = Color.blue,
			COLOR_CIRCULO_ARISTA_MALA = Color.red,
			COLOR_TRIANGULO = Color.green;
	
	public Delaunay(Point n, Point se, Point sw, int ret) {
		setCapacidadAristas(INIT);
		segmentNum = 0;
		segmentList = new Vector<Segment>();

		points = new HashSet<Point>();

		triGraph = new Graph<Triangle>();

		this.n = n;
		this.se = se;
		this.sw = sw;
		initialTriangle = new Triangle(n, se, sw);

		triGraph.add(initialTriangle);
	}

	public void inicializar() {
		setCapacidadAristas(INIT);
		segmentNum = 0;
		segmentList = new Vector<Segment>();

		points = new HashSet<Point>();

		triGraph = new Graph<Triangle>();

		n = new Point(0, -3000);
		se = new Point(4000, 2000);
		sw = new Point(-2000, 2000);

		initialTriangle = new Triangle(sw, n, se);

		Segment e1 = new Segment(sw, null, null);
		Segment e2 = new Segment(n, null, null);
		Segment e3 = new Segment(se, null, null);
		Segment e4 = new Segment(sw, null, null);
		Segment e5 = new Segment(n, null, null);
		Segment e6 = new Segment(se, null, null);

		e1.setSig(e3);
		e3.setSig(e5);
		e5.setSig(e1);

		e1.setTwin(e2);
		e3.setTwin(e4);
		e5.setTwin(e6);

		addSegment(e1);
		addSegment(e2);
		addSegment(e3);
		addSegment(e4);
		addSegment(e5);
		addSegment(e6);

		triGraph.add(initialTriangle);
	}
	
	public void insertarVertice(Point v) {
		if (yaExistia(v))
			return; 
		points.add(v);

		Segment e = enQueTriangulo(v); 
		Segment e1 = new Segment(v, null, null);
		Segment e2 = new Segment(e.getDest(), null, null);
		Segment e3 = new Segment(v, null, null);
		Segment e4 = new Segment(e.getSig().getDest(), null, null);
		Segment e5 = new Segment(v, null, null);
		Segment e6 = new Segment(e.getTwin().getDest(), null, null);

		e1.setSig(e6);
		e2.setSig(e.getSig());
		e3.setSig(e2);
		e4.setSig(e.getSig().getSig());
		e5.setSig(e4);
		e6.setSig(e);
		e.getSig().getSig().setSig(e5);
		e.getSig().setSig(e3);
		e.setSig(e1);

		e1.setTwin(e2);
		e3.setTwin(e4);
		e5.setTwin(e6);

		addSegment(e1);
		addSegment(e2);
		addSegment(e3);
		addSegment(e4);
		addSegment(e5);
		addSegment(e6);

		legaliza(e6.getSig()); 
		legaliza(e2.getSig()); 
		legaliza(e4.getSig()); 

	}

	public void insertarVertice2(Point v) {
		if (yaExistia(v))
			return; 

		points.add(v);

		Segment e = enQueTriangulo(v); 

		Triangle triangle = null;

		for (Triangle tri : triGraph.nodeSet()) {
			if (v.isOutside(tri.toArray(new Point[0])) == null) {
				triangle = tri;
				break;
			}
		}
		if (triangle == null)
			System.out.println("non trovato");

		Segment e1 = new Segment(v, null, null);
		Segment e2 = new Segment(e.getDest(), null, null);
		Segment e3 = new Segment(v, null, null);
		Segment e4 = new Segment(e.getSig().getDest(), null, null);
		Segment e5 = new Segment(v, null, null);
		Segment e6 = new Segment(e.getTwin().getDest(), null, null);

		e1.setSig(e6);
		e2.setSig(e.getSig());
		e3.setSig(e2);
		e4.setSig(e.getSig().getSig());
		e5.setSig(e4);
		e6.setSig(e);
		e.getSig().getSig().setSig(e5);
		e.getSig().setSig(e3);
		e.setSig(e1);

		e1.setTwin(e2);
		e3.setTwin(e4);
		e5.setTwin(e6);

		addSegment(e1);
		addSegment(e2);
		addSegment(e3);
		addSegment(e4);
		addSegment(e5);
		addSegment(e6);

		Triangle triangle1 = new Triangle(triangle.get(0), triangle.get(1), v);
		Triangle triangle2 = new Triangle(triangle.get(1), triangle.get(2), v);
		Triangle triangle3 = new Triangle(triangle.get(0), v, triangle.get(2));

		triGraph.add(triangle1);
		triGraph.add(triangle2);
		triGraph.add(triangle3);

		for (Triangle neighbor : triGraph.neighbors(triangle)) {
			if (triangle1.isNeighbor(neighbor)) {
				triGraph.add(triangle1, neighbor);
			}
			if (triangle2.isNeighbor(neighbor)) {
				triGraph.add(triangle2, neighbor);
			}
			if (triangle3.isNeighbor(neighbor)) {
				triGraph.add(triangle3, neighbor);
			}
		}

		triGraph.add(triangle1, triangle2);
		triGraph.add(triangle1, triangle3);
		triGraph.add(triangle2, triangle3);
		triGraph.remove(triangle);

		legaliza(v, triangle1.facetOpposite(v), triangle1);
		legaliza(v, triangle2.facetOpposite(v), triangle2);
		legaliza(v, triangle3.facetOpposite(v), triangle3);

		legaliza(e6.getSig()); 
		legaliza(e2.getSig()); 
		legaliza(e4.getSig()); 
	}

	public void insertarVertice3(Point v) {
		if (points.contains(v))
			return;
		points.add(v);

		Triangle triangle = null;
		int[] rel = null;
		int inside = -1;
		for (Triangle tri : triGraph.nodeSet()) {
			rel = tri.getRelations(v);
			if (rel[0] == 1 && rel[1] == 1 && rel[2] == 1) {
				triangle = tri;
				inside = 1;
				break;
			} else if (rel[0] == 0 || rel[1] == 0 || rel[2] == 0) {
				triangle = tri;
				inside = 0;
				break;
			}
			
		}
		switch (inside){
		case 1:
			Triangle triangle1 = new Triangle(triangle.get(0), triangle
					.get(1), v);
			Triangle triangle2 = new Triangle(triangle.get(1), triangle
					.get(2), v);
			Triangle triangle3 = new Triangle(triangle.get(0), v, triangle
					.get(2));

			triGraph.add(triangle1);
			triGraph.add(triangle2);
			triGraph.add(triangle3);

			for (Triangle neighbor : triGraph.neighbors(triangle)) {
				if (triangle1.isNeighbor(neighbor)) {
					triGraph.add(triangle1, neighbor);
				}
				if (triangle2.isNeighbor(neighbor)) {
					triGraph.add(triangle2, neighbor);
				}
				if (triangle3.isNeighbor(neighbor)) {
					triGraph.add(triangle3, neighbor);
				}
			}

			triGraph.add(triangle1, triangle2);
			triGraph.add(triangle1, triangle3);
			triGraph.add(triangle2, triangle3);
			triangle.removeReferencesToPoints();
			triGraph.remove(triangle);

			legaliza2(v, triangle1.facetOpposite(v), triangle1);
			legaliza2(v, triangle2.facetOpposite(v), triangle2);
			legaliza2(v, triangle3.facetOpposite(v), triangle3);
			break;
		case 0:
			@SuppressWarnings("unused")
			Point pi = null, pj = null, pk = null, pl;
			if (rel[0] == 0) {
				pi = triangle.getSorted(0);
				pj = triangle.getSorted(1);
				pk = triangle.getSorted(2);
			} else if (rel[1] == 0) {
				pi = triangle.getSorted(1);
				pj = triangle.getSorted(2);
				pk = triangle.getSorted(0);
			} else if (rel[2] == 0) {
				pi = triangle.getSorted(2);
				pj = triangle.getSorted(0);
				pk = triangle.getSorted(1);
			}
			pl = neighborOpposite(pk, triangle).getVertexButNot(pi, pj);
			points.remove(v);
			break;
		}
	}

	private void legaliza2(Point point, ArraySet<Point> facetOpposite,
			Triangle triangle) {
		if (initialTriangle.containsAll(facetOpposite))
			return;
		Triangle opposite = neighborOpposite(point, triangle);
		if (opposite == null) {
			System.out.println(point);
			System.out.println(triangle);
		} else if ((opposite.getVertexButNot(new Point[] {
				facetOpposite.get(0), facetOpposite.get(1) }))
				.vsCircumcircle(triangle.toArray(new Point[0])) == -1) {

			Triangle[] news = flip2(triangle, opposite, facetOpposite);
			legaliza2(point, news[0].facetOpposite(point), news[0]);
			legaliza2(point, news[1].facetOpposite(point), news[1]);
		}

	}

	private void legaliza(Point v, ArraySet<Point> facetOpposite,
			Triangle triangle1) {
		for (Segment seg : facetOpposite.get(0).getEdges()) {
			if (seg.getTwin().getDest().equals(facetOpposite.get(1))) {
				if (seg.getSig() != null
						&& seg.getSig().getDest().equals(
								triangle1
										.getVertexButNot(new Point[] {
												seg.getTwin().getDest(),
												seg.getDest() })))
					legaliza(v, seg, triangle1);
				else if (seg.getSig() == null
						&& seg.getTwin().getSig().getDest().equals(
								triangle1
										.getVertexButNot(new Point[] {
												seg.getTwin().getDest(),
												seg.getDest() })))
					legaliza(v, seg.getTwin(), triangle1);
				break;
			}
		}
	}

	/**
	 * Report neighbor opposite the given vertex of triangle.
	 * 
	 * @param site
	 *            a vertex of triangle
	 * @param triangle
	 *            we want the neighbor of this triangle
	 * @return the neighbor opposite site in triangle; null if none
	 * @throws IllegalArgumentException
	 *             if site is not in this triangle
	 */
	public Triangle neighborOpposite(Point site, Triangle triangle) {
		if (!triangle.contains(site))
			throw new IllegalArgumentException("Bad vertex; not in triangle");
		for (Triangle neighbor : triGraph.neighbors(triangle)) {
			if (!neighbor.contains(site))
				return neighbor;
		}
		return null;
	}

	/**
	 * Report triangles surrounding site in order (cw or ccw).
	 * 
	 * @param site
	 *            we want the surrounding triangles for this site
	 * @param triangle
	 *            a "starting" triangle that has site as a vertex
	 * @return all triangles surrounding site in order (cw or ccw)
	 * @throws IllegalArgumentException
	 *             if site is not in triangle
	 */
	public List<Triangle> surroundingTriangles(Point site, Triangle triangle) {
		if (!triangle.contains(site))
			throw new IllegalArgumentException("Site not in triangle");
		List<Triangle> list = new ArrayList<Triangle>();
		Triangle start = triangle;
		Point guide = triangle.getVertexButNot(site); // Affects cw or ccw
		while (true) {
			list.add(triangle);
			Triangle previous = triangle;
			triangle = this.neighborOpposite(guide, triangle); // Next triangle
			guide = previous.getVertexButNot(site, guide); // Update guide
			if (triangle == start)
				break;
		}
		return list;
	}

	private Triangle getOpposite(Triangle triangle, Point v) {
		for (Triangle neig : triGraph.neighbors(triangle)) {
			if (neig.contains(triangle.facetOpposite(v).get(0))
					&& neig.contains(triangle.facetOpposite(v).get(1))) {
				return neig;
			}
		}
		return null;
	}

	public void legaliza(Point point, Segment segment, Triangle triangle) {
		if (aristaFicticia(segment))
			return;
		if (dentroDeCirculo(segment.getDest(), segment.getSig().getDest(),
				segment.getTwin().getDest(), segment.getTwin().getSig()
						.getDest())) {
			Triangle[] news = flip(triangle, neighborOpposite(point, triangle),
					segment);

			flip(segment);

			legaliza(point, news[0].facetOpposite(point), news[0]);
			legaliza(point, news[1].facetOpposite(point), news[1]);
		}

	}

	private void legaliza(Segment e) {
		if (aristaFicticia(e))
			return;

		if (dentroDeCirculo(e.getDest(), e.getSig().getDest(), e.getTwin()
				.getDest(), e.getTwin().getSig().getDest())) {

			flip(e);

			legaliza(e.getSig().getSig());
			legaliza(e.getTwin().getSig());
		}
	}

	public int getSegmentNum() {
		return segmentNum;
	}

	public Vector<Segment> getSegmentList() {
		return segmentList;
	}

	public HashSet<Point> getPoints() {
		return points;
	}

	public HashSet<Point> getPoints2() {
		HashSet<Point> tmp = new HashSet<Point>();
		for (int i = 0; i < segmentList.size(); i++) {
			Point tmpPoint = segmentList.get(i).getDest();

			tmp.add(tmpPoint);
			if (!segmentList.get(i).getTwin().getDest().equals(n)
					&& !segmentList.get(i).getTwin().getDest().equals(se)
					&& !segmentList.get(i).getTwin().getDest().equals(sw)) {
				segmentList.get(i).getDest().addEdge(segmentList.get(i));
			}

		}
		tmp.remove(n);
		tmp.remove(se);
		tmp.remove(sw);
		return tmp;
	}

	public Triangle locatePoint(Point point) {
		Triangle tmp = null;
		for (Triangle tr : n.getTriangles()) {
			if (tr.contains(sw)) {
				tmp = tr;
				if (tmp.contains(se))
					return tmp;
				break;
			}
		}
		Point start = new Point(0, 0);
		Point a = n;
		while (isOnLeft(point, a, tmp.getNextInCCW(a))) {
			if (isOnLeft(tmp.getNextInCCW(tmp.getNextInCCW(a)), start, point)) {

				Point futurea = tmp.getNextInCCW(tmp.getNextInCCW(a));
				tmp = getOpposite(tmp, a);
				a = futurea;
			} else {
				Point futurea = tmp.getNextInCCW(tmp.getNextInCCW(a));
				tmp = getOpposite(tmp, a);
				a = futurea;
			}
		}
		return tmp;

	}

	public Segment enQueTriangulo(Point t)
	{
		Point start = new Point(0, 0);
		Segment e = segmentList.get(0);

		while (isOnLeft(t, e.getTwin().getDest(), e.getDest())) {
			if (isOnLeft(e.getSig().getDest(), start, t)) {
				e = e.getSig().getTwin();
			} else {
				e = e.getSig().getSig().getTwin();
			}
		}
		return e.getTwin();
	}

	public int getNumAristas() {
		return segmentNum;
	}

	public Segment getEdge(int i) {
		return segmentList.get(i);
	}

	public void addSegment(Segment e)
	{
		segmentList.add(e);
		segmentNum++;
	}

	private boolean isOnLeft(Point t, Point a, Point b) {
		return (a.getX() * (b.getY() - t.getY()) - a.getY()
				* (b.getX() - t.getX())
				+ ((b.getX() * t.getY()) - (b.getY() * t.getX())) > 0);
	}

	public boolean aristaFicticia(Segment e)
	{
		for (int i = 0; i < 6; i++) {
			if (e == segmentList.get(i))
				return true;
		}
		return false;
	}

	public boolean dentroDeCirculo(Point p, Point q, Point r, Point s) {
		double ax = q.getX() - p.getX();
		double ay = q.getY() - p.getY();
		double aa = (ax * ax) + (ay * ay);
		double bx = r.getX() - p.getX();
		double by = r.getY() - p.getY();
		double bb = (bx * bx) + (by * by);
		double cx = s.getX() - p.getX();
		double cy = s.getY() - p.getY();
		double cc = (cx * cx) + (cy * cy);
		return ((aa * (bx * cy - by * cx) - bb * (ax * cy - ay * cx) + cc
				* (ax * by - ay * bx)) < 0);
	}

	public Point centroCirculo(Point p, Point q, Point r) {
		double px = (double) p.getX();
		double py = -(double) p.getY();
		double qx = (double) q.getX();
		double qy = -(double) q.getY();
		double rx = (double) r.getX();
		double ry = -(double) r.getY();
		double a1 = -0.5 * ((px * px) - (qx * qx) + (py * py) - (qy * qy));
		double b1 = px - qx;
		double c1 = py - qy;
		double a2 = -0.5 * ((qx * qx) - (rx * rx) + (qy * qy) - (ry * ry));
		double b2 = qx - rx;
		double c2 = qy - ry;
		double w = (b1 * c2) - (b2 * c1);
		double x = -((a1 * c2) - (a2 * c1));
		double y = (a1 * b2) - (a2 * b1);
		Point v = new Point((int) (x / w), (int) (y / w));
		return v;
	}

	public void flip(Segment e) {
		e.setDest(e.getSig().getDest());
		e.getTwin().setDest(e.getTwin().getSig().getDest());
		e.getSig().getSig().setSig(e.getTwin().getSig());
		e.getTwin().getSig().getSig().setSig(e.getSig());
		e.setSig(e.getSig().getSig());
		e.getTwin().setSig(e.getTwin().getSig().getSig());
		e.getSig().getSig().setSig(e);
		e.getTwin().getSig().getSig().setSig(e.getTwin());
	}

	public Triangle[] flip(Triangle first, Triangle second, Segment segment) {
		Point firstOpposite = first.getVertexButNot(new Point[] {
				segment.getDest(), segment.getTwin().getDest() });
		Point secondOpposite = second.getVertexButNot(new Point[] {
				segment.getDest(), segment.getTwin().getDest() });

		ArraySet<Point> set = first.facetOpposite(segment.getDest());
		set.add(secondOpposite);
		Triangle triangle1 = new Triangle(set);
		set = second.facetOpposite(segment.getTwin().getDest());
		set.add(firstOpposite);
		Triangle triangle2 = new Triangle(set);

		triGraph.add(triangle1);
		triGraph.add(triangle2);
		triGraph.add(triangle1, triangle2);

		Set<Triangle> neighbors = triGraph.neighbors(first);
		for (Triangle neig : neighbors) {
			if (first.isNeighbor(neig)) {
				triGraph.add(triangle1, neig);
			}
			if (second.isNeighbor(neig)) {
				triGraph.add(triangle2, neig);
			}
		}
		neighbors = triGraph.neighbors(second);
		for (Triangle neig : neighbors) {
			if (first.isNeighbor(neig)) {
				triGraph.add(triangle1, neig);
			}
			if (second.isNeighbor(neig)) {
				triGraph.add(triangle2, neig);
			}
		}

		triGraph.remove(first);
		triGraph.remove(second);

		return new Triangle[] { triangle1, triangle2 };
	}

	public Triangle[] flip2(Triangle first, Triangle second,
			ArraySet<Point> facetOpposite) {
		Point firstOpposite = first.getVertexButNot(new Point[] {
				facetOpposite.get(0), facetOpposite.get(1) });
		Point secondOpposite = second.getVertexButNot(new Point[] {
				facetOpposite.get(0), facetOpposite.get(1) });

		ArraySet<Point> set = first.facetOpposite(facetOpposite.get(0));
		set.add(secondOpposite);
		Triangle triangle1 = new Triangle(set);
		set = second.facetOpposite(facetOpposite.get(1));
		set.add(firstOpposite);
		Triangle triangle2 = new Triangle(set);

		if (triangle1.containsAll(triangle2)) {
			System.out.println("AHI AHIA AHI");
		}

		triGraph.add(triangle1);
		triGraph.add(triangle2);
		triGraph.add(triangle1, triangle2);
		triGraph.add(triangle2, triangle1);

		Set<Triangle> neighbors = new HashSet<Triangle>();
		neighbors.addAll(triGraph.neighbors(first));
		neighbors.addAll(triGraph.neighbors(second));
		for (Triangle neig : neighbors) {

			if (triangle1.isNeighbor(neig)) {
				triGraph.add(triangle1, neig);
			}
			if (triangle2.isNeighbor(neig)) {
				triGraph.add(triangle2, neig);
			}

		}
		first.removeReferencesToPoints();
		second.removeReferencesToPoints();
		triGraph.remove(first);
		triGraph.remove(second);

		return new Triangle[] { triangle1, triangle2 };
	}

	public boolean yaExistia(Point v)
	{
		for (int i = 0; i < segmentNum; i++) {
			if (segmentList.get(i).getDest().getX() == v.getX()
					&& segmentList.get(i).getDest().getY() == v.getY()) {
				return true;
			}
		}
		return false;
	}

	public Vector<Segment> getSegmentList(Point pnt) {
		Vector<Segment> tmp = new Vector<Segment>();
		for (int i = 0; i < segmentNum; i = i + 1) {
			if (segmentList.get(i).getTwin().getDest().equals(pnt)) {
				tmp.add(segmentList.get(i));
			}
		}
		return tmp;
	}

	public HashSet<Triangle> getTriangles(Point pnt) {
		HashSet<Triangle> triangles = new HashSet<Triangle>();
		Vector<Segment> tmp = getSegmentList(pnt);
		for (int i = 0; i < tmp.size(); i++) {
			Triangle tr = new Triangle(tmp.get(i).getDest(), tmp.get(i)
					.getSig().getDest(), tmp.get(i).getSig().getSig().getDest());
			boolean add = true;
			for (Triangle tmptr : triangles) {
				if (tmptr.hasSameVertices(tr)) {
					// System.out.println(tr);
					add = false;
				}
			}
			if (add)
				triangles.add(tr);
		}
		return triangles;
	}

	public HashSet<Triangle> getTriangles2(Point pnt) {
		getTriangles2();
		HashSet<Triangle> tmptriangles = new HashSet<Triangle>();
		for (Triangle tr : triangles) {
			if (tr.contains(pnt))
				tmptriangles.add(tr);
		}
		return tmptriangles;
	}

	public HashSet<Triangle> getTriangles2() {
		if (triangles == null) {
			System.out.println("Calcolando triangoli");
			triangles = new HashSet<Triangle>();
			for (int i = 6; i < segmentList.size(); i = i + 1) {
				@SuppressWarnings("unused")
				Triangle tr = new Triangle(segmentList.get(i).getDest(),
						segmentList.get(i).getSig().getDest(), segmentList.get(
								i).getSig().getSig().getDest());
			}
		}
		return triangles;
	}

	public Set<Triangle> getTriangles3() {
		return triGraph.nodeSet();
	}

	public HashSet<Triangle> getTriangles() {
		HashSet<Triangle> triangles = new HashSet<Triangle>();
		Vector<HashSet<Segment>> links = new Vector<HashSet<Segment>>();
		links.setSize(segmentList.size());
		for (int i = 0; i < segmentList.size(); i = i + 1) {
			links.set(i, new HashSet<Segment>());
			for (int j = 0; j < segmentList.size(); j = j + 1) {
				if (segmentList.get(i).getDest().equals(
						segmentList.get(j).getTwin().getDest())
						&& !segmentList.get(i).equals(
								segmentList.get(j).getTwin())) {
					links.get(i).add(segmentList.get(j));
				}
			}
		}
		for (int i = 0; i < segmentList.size(); i++) {
			for (int j = 0; j < segmentList.size(); j++) {
				for (Segment seg : links.get(j)) {
					if (segmentList.get(i).getTwin().getDest().equals(
							segmentList.get(j).getTwin().getDest())
							&& segmentList.get(i).getDest().equals(
									seg.getDest())) {
						Triangle tr = new Triangle(segmentList.get(i).getTwin()
								.getDest(), segmentList.get(j).getDest(),
								segmentList.get(i).getDest());
						boolean add = true;
						for (Triangle tmptr : triangles) {
							if (tmptr.hasSameVertices(tr)) {
								add = false;
							}
						}
						if (add)
							triangles.add(tr);
					}

				}
			}
		}
		return triangles;
	}

	public Point getN() {
		return n;
	}

	public Point getSe() {
		return se;
	}

	public Point getSw() {
		return sw;
	}

	public void setCapacidadAristas(int capacidadAristas) {
		this.capacidadAristas = capacidadAristas;
	}

	public int getCapacidadAristas() {
		return capacidadAristas;
	}
}
